package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.完全背包DP;

import java.util.Scanner;
public class dp_1023 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int[] values =  {0,10,20,50,100};
        int N = 4;
        int n = in.nextInt();
        int[][] dp = new int[N + 1][n + 1];
        //dp[i][j]：表示所有从前i个物品中选k个，但总价值等于j的方案数
        //所有从前i个数中选，和为0的方案数都默认为1，即都不选也为一种方案
        for (int i = 0; i <= N; i++)dp[i][0] = 1;
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= n; j++){
                for (int k = 0; values[i] * k <= j; k++){
                    //当前的方案数 = 选当前数的方案数 + 不选当前数的方案数
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - k * values[i]] + dp[i][j]);
                }
            }
        }
        System.out.print(dp[4][n]);
    }
}
/*
小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）
输入格式

一个整数 n，代表总共钱数。
输出格式

一个整数，代表选择方案种数。
数据范围

0≤n≤1000

输入样例1：

20

输出样例1：

2

输入样例2：

15

输出样例2：

0

输入样例3：

0

输出样例3：

1

 */